package com.zlm.linked;

import java.util.Objects;

/**
 * @author zlm
 * @date 2025/4/28
 * <p>
 * 循环链表（环形）
 */
public class CycleLinkedNode {

    public static void main(String[] args) {
        //CycleNode<Integer> root = new CycleNode<>(null, 1);
        //root.next = root;
        //
        //addNode(root, 100);
        //printNode(root);
        //addNode(root, 200);
        //printNode(root);
        ////删除节点
        //deleteEndNode(root);
        //deleteEndNode(root);
        //printNode(root);
        josephus(41,3);
    }

    /**
     * 删除指定位置节点
     * @param head
     * @param k
     * @param <E>
     */
    public static <E> CycleNode<E> deleteNode(CycleNode<E> head, int k){
        if(head == null || head.next == null){
            return head;
        }
        if(k == 0){
            //删除头节点
            CycleNode<E> current = head;
            while (current.next != head){
                current = current.next;
            }
            current.next = head.next;
            return head;
        }
        CycleNode<E> current = head;
        for (int i = 0; i < k - 1; i++) {
            current = current.next;
        }
        CycleNode<E> tmp = current.next;
        current.next = current.next.next;

        return tmp;

    }

    /**
     * 约瑟夫问题
     * @param n
     * @param m
     */
    public static void josephus(int n,int m){
        CycleNode<Integer> head = new CycleNode<>(null,1);
        head.next = head;
        for (int i = 1; i < n; i++) {
            addNode(head,i+1);
        }
        printNode(head);
        for (int i = 0; i < n; i++) {
            CycleNode<Integer> node = deleteNode(head, m - 1);
            System.out.print(node.value +"\t");
            head = node.next;
        }
    }

    /**
     * 删除尾节点
     * @param head
     * @param <E>
     */
    public static <E> void deleteEndNode(CycleNode<E> head) {
        if(head == null || head.next == head){
            return;
        }
        CycleNode<E> current = head;
        //找到链表倒数第二个节点
        while (current.next.next != head){
            current = current.next;
        }
        current.next.next = null;
        current.next = head;

    }

    /**
     * 打印节点
     * @param head
     * @param <E>
     */
    public static <E> void printNode(CycleNode<E> head) {
        if (head == null) {
            return;
        }
        CycleNode<E> current = head.next;
        if(current == head){
            System.out.print(current.value + "\t");
            return;
        }
        System.out.print(head.value + "\t");
        while (current != head) {
            System.out.print(current.value + "\t");
            current = current.next;
        }
        System.out.println();
    }

    /**
     * 添加节点
     *
     * @param head
     * @param value
     * @param <E>
     */
    public static <E> void addNode(CycleNode<E> head, E value) {
        if (head == null) {
            return;
        }
        CycleNode<E> current = head;

        while (current.next != head) {
            current = current.next;
        }
        current.next = new CycleNode<>(head, value);
    }

    static class CycleNode<E> {
        E value;
        CycleNode<E> next;

        public CycleNode(CycleNode<E> node, E value) {
            this.value = value;
            this.next = node;
        }
    }

}
